【题解】 [HNOI2016]序列 莫队+ST表 luoguP3246 | Qiuly's blog!

【题解】 [HNOI2016]序列 莫队+ST表 luoguP3246

Posted on | Edited on | In | Comments:

一道莫队……….

最主要的就是怎么从当前区间推到相邻区间。

假设当前区间为 $[l,r]$ ，目标区间为 $[l,r+1]$ 。那么很显然这样子就会增加：

这些区间，现在我们要做的就是尽快的算出这些区间的答案。

假设 $p$ 为区间 $[l,r+1]$ 的最小值的位置，那么在上面的区间中，$[l,r+1] \cdots [p,r+1]$ 这些区间显然都包含了 $p$ ，也就是说这些区间的最小值都为 $p$ ，那么这一段区间的贡献显然为 $a[p]\cdot (p-l+1)$ ，其中 $a[p]$ 为 $p$ 位置上的权值。

很显然我们可以预处理一个 $ST$ 表，通过 $ST$ 表上面的 $p$ 就可以 $O(1)$ 求出。

然后接下来考虑剩下的 $[p+1,r+1]\cdots [r+1,r+1]$ 这些区间。

我们设 $f[i][j]$ 表示右端点为 $j$ ，左端点的位置在 $[i,j]$ 范围内的所有区间所造成的贡献。

我们可以用单调栈预处理出位置 $i$ 的 $lmin$ 和 $rmin$ ，$lmin[i]$ 表示 $i$ 往左走遇到的第一个比 $i$ 小的数的位置，$rmin$ 同理。

那么我们很轻易的可以得到：

发现 $i$ 是没有影响的，于是我们将 $i$ 丢掉。

这个式子 $DP$ 与处理一下就好了。

那么最后我们从 $[l,r]$ 移向 $[l,r+1]$ 产生的贡献为：

至于为什么要减去 $f[p]$ ，差不多是容斥的道理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>

#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
typedef long long ll;

const int N=1e5+2;
const int inf=1e9+9;

int n,m,block,a[N];
struct MO{int l,r,id;}q[N];
int top,stack[N],lmin[N],rmin[N];
ll res,Ans[N],fl[N],fr[N];

bool cmp(MO a,MO b){
    return a.l/block==b.l/block?a.l/block&1?a.r<b.r:a.r>b.r:a.l/block<b.l/block;
}

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
} 

namespace ST{
    const int LogN=23;
    int logs[N],f[N][LogN+2];
    inline void Make(){
        logs[0]=-1;
        for(int i=1;i<=n;++i)
            f[i][0]=i,logs[i]=logs[i>>1]+1;
        for(int j=1;j<=logs[n];++j)
            for(int i=1;i+(1<<j)-1<=n;++i)
                f[i][j]=a[f[i][j-1]]<a[f[i+(1<<(j-1))][j-1]]?f[i][j-1]:f[i+(1<<(j-1))][j-1];
    }
    inline ll query(int x,int y){
        int ans=logs[y-x+1];
        return a[f[x][ans]]<a[f[y-(1<<ans)+1][ans]]?f[x][ans]:f[y-(1<<ans)+1][ans];
    }
}

inline void __Pre_lmin_rmin(){
    for(int i=1;i<=n;++i){
        while(top&&a[stack[top]]>a[i])
            rmin[stack[top--]]=i;
        lmin[i]=stack[top],stack[++top]=i;
    }while(top)lmin[stack[top]]=stack[top-1],rmin[stack[top--]]=n+1;
}

inline ll left(int l,int r){
    int p=ST::query(l-1,r);
    return (ll)a[p]*(r-p+1)+fl[l-1]-fl[p];
}
inline ll right(int l,int r){
    int p=ST::query(l,r+1);
    return (ll)a[p]*(p-l+1)+fr[r+1]-fr[p];
} 

int main(){
    IN(n),IN(m);block=sqrt(n);
    a[0]=a[n+1]=inf;
    for(int i=1;i<=n;++i)IN(a[i]);
    __Pre_lmin_rmin();
    ST::Make();
    for(int i=1;i<=n;++i)fr[i]=(ll)a[i]*(i-lmin[i])+fr[lmin[i]];
    for(int i=n;i>=1;--i)fl[i]=(ll)a[i]*(rmin[i]-i)+fl[rmin[i]];
    for(int i=1;i<=m;++i)
        IN(q[i].l),IN(q[i].r),q[i].id=i;
    std::sort(q+1,q+1+m,cmp);
    int L=q[1].l,R=L-1;res=0;
    for(int i=1;i<=m;++i){
        int x=q[i].l,y=q[i].r;
        while(L>x)res+=left(L,R),L--;
        while(R<y)res+=right(L,R),R++;
        while(L<x)res-=left(L+1,R),++L;
        while(R>y)res-=right(L,R-1),--R;
        Ans[q[i].id]=res;
    }
    for(int i=1;i<=m;++i)
       printf("%lld\n",Ans[i]);
    return 0;
}

本文标题:【题解】 [HNOI2016]序列 莫队+ST表 luoguP3246

文章作者:Qiuly

发布时间:2019年03月14日 - 00:00

最后更新:2019年03月29日 - 13:54

原始链接:http://qiulyblog.github.io/2019/03/14/[题解]luoguP3246/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。